package edu.wust;

//在英国，货币是由英镑 ￡，便士 p 构成的。一共有八种钱币在流通：
//        1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) 和 ￡2 (200p).
//        要构造 ￡2 可以用如下方法：
//        1×￡1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
//        允许使用任意数目的钱币，一共有多少种构造 ￡2 的方法？
//        答案：73682
public class exam31 {
    static int count=1;    //200本身算一种
    public static void tf(int[] num,int begin,int last){
        if(begin<0)
            return;
        int circle=num[7]/num[begin];
        for(int i=circle;i>=0;--i){
            int temp=last-num[begin]*i;
            if(temp==0){
                count++;
            }
            else{
                tf(num,begin-1,temp);
            }
        }
    }
    public static void main(String[] args) {
        int[] num=new int[8];
        num[0]=1;num[1]=2;num[2]=5;num[3]=10;num[4]=20;num[5]=50;num[6]=100;num[7]=200;
        for(int i=6;i>=0;--i){
            int circle=num[7]/num[i];
            for(int j=circle;j>0;--j){
                int temp=200-num[i]*j;
                if(temp==0){
                    count++;
                }
                else{
                    tf(num,i-1,temp);
                }
            }
        }
        System.out.println(count);
    }
}

